<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
        "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html id="htmlId">
<head>
    <title>Coverage Report :: Navigation</title>
    <style type="text/css">
        @import "../../.css/coverage.css";
    </style>
</head>

<body>
<div class="header"></div>

<div class="content">
    <div class="breadCrumbs">
        [ <a href="../../index.html">all classes</a> ]
        [ <a href="../index.html">nl.tudelft.jpacman.npc.ghost</a> ]
    </div>

    <h1>Coverage Summary for Class: Navigation (nl.tudelft.jpacman.npc.ghost)</h1>

    <table class="coverageStats">

        <tr>
            <th class="name">Class</th>
            <th class="coverageStat
">
                Method, %
            </th>
            <th class="coverageStat
">
                Line, %
            </th>
        </tr>
        <tr>
            <td class="name">Navigation</td>
            <td class="coverageStat">
  <span class="percent">
    0%
  </span>
                <span class="absValue">
    (0/ 7)
  </span>
            </td>
            <td class="coverageStat">
  <span class="percent">
    0%
  </span>
                <span class="absValue">
    (0/ 49)
  </span>
            </td>
        </tr>
        <tr>
            <td class="name">Navigation$Node</td>
            <td class="coverageStat">
  <span class="percent">
    0%
  </span>
                <span class="absValue">
    (0/ 6)
  </span>
            </td>
            <td class="coverageStat">
  <span class="percent">
    0%
  </span>
                <span class="absValue">
    (0/ 13)
  </span>
            </td>
        </tr>
        <tr>
            <td class="name"><strong>total</strong></td>
            <td class="coverageStat">
  <span class="percent">
    0%
  </span>
                <span class="absValue">
    (0/ 13)
  </span>
            </td>
            <td class="coverageStat">
  <span class="percent">
    0%
  </span>
                <span class="absValue">
    (0/ 62)
  </span>
            </td>
        </tr>
    </table>

    <br/>
    <br/>


    <div class="sourceCode"><i>1</i>&nbsp;package nl.tudelft.jpacman.npc.ghost;
        <i>2</i>&nbsp;
        <i>3</i>&nbsp;import java.util.ArrayList;
        <i>4</i>&nbsp;import java.util.HashSet;
        <i>5</i>&nbsp;import java.util.List;
        <i>6</i>&nbsp;import java.util.Set;
        <i>7</i>&nbsp;
        <i>8</i>&nbsp;import nl.tudelft.jpacman.board.Board;
        <i>9</i>&nbsp;import nl.tudelft.jpacman.board.Direction;
        <i>10</i>&nbsp;import nl.tudelft.jpacman.board.Square;
        <i>11</i>&nbsp;import nl.tudelft.jpacman.board.Unit;
        <i>12</i>&nbsp;
        <i>13</i>&nbsp;/**
        <i>14</i>&nbsp; * Navigation provides utility to navigate on {@link Square}s.
        <i>15</i>&nbsp; *
        <i>16</i>&nbsp; * @author Jeroen Roosen
        <i>17</i>&nbsp; */
        <b class="nc"><i>18</i>&nbsp;public final class Navigation {</b>
        <i>19</i>&nbsp;
        <b class="nc"><i>20</i>&nbsp; private Navigation() {</b>
        <i>21</i>&nbsp; }
        <i>22</i>&nbsp;
        <i>23</i>&nbsp; /**
        <i>24</i>&nbsp; * Calculates the shortest path. This is done by BFS. This search ensures
        <i>25</i>&nbsp; * the traveller is allowed to occupy the squares on the way, or returns the
        <i>26</i>&nbsp; * shortest path to the square regardless of terrain if no traveller is
        <i>27</i>&nbsp; * specified.
        <i>28</i>&nbsp; *
        <i>29</i>&nbsp; * @param from
        <i>30</i>&nbsp; * The starting square.
        <i>31</i>&nbsp; * @param to
        <i>32</i>&nbsp; * The destination.
        <i>33</i>&nbsp; * @param traveller
        <i>34</i>&nbsp; * The traveller attempting to reach the destination. If
        <i>35</i>&nbsp; * traveller is set to &lt;code&gt;null&lt;/code&gt;, this method will ignore
        <i>36</i>&nbsp; * terrain and find the shortest path whether it can actually be
        <i>37</i>&nbsp; * reached or not.
        <i>38</i>&nbsp; * @return The shortest path to the destination or &lt;code&gt;null&lt;/code&gt; if no
        <i>39</i>&nbsp; * such path could be found. When the destination is the current
        <i>40</i>&nbsp; * square, an empty list is returned.
        <i>41</i>&nbsp; */
        <i>42</i>&nbsp; public static List&lt;Direction&gt; shortestPath(Square from, Square to,
        <i>43</i>&nbsp; Unit traveller) {
        <b class="nc"><i>44</i>&nbsp; if (from.equals(to)) {</b>
        <b class="nc"><i>45</i>&nbsp; return new ArrayList&lt;&gt;();</b>
        <i>46</i>&nbsp; }
        <i>47</i>&nbsp;
        <b class="nc"><i>48</i>&nbsp; List&lt;Node&gt; targets = new ArrayList&lt;&gt;();</b>
        <b class="nc"><i>49</i>&nbsp; Set&lt;Square&gt; visited = new HashSet&lt;&gt;();</b>
        <b class="nc"><i>50</i>&nbsp; targets.add(new Node(null, from, null));</b>
        <b class="nc"><i>51</i>&nbsp; while (!targets.isEmpty()) {</b>
        <b class="nc"><i>52</i>&nbsp; Node node = targets.remove(0);</b>
        <b class="nc"><i>53</i>&nbsp; Square square = node.getSquare();</b>
        <b class="nc"><i>54</i>&nbsp; if (square.equals(to)) {</b>
        <b class="nc"><i>55</i>&nbsp; return node.getPath();</b>
        <i>56</i>&nbsp; }
        <b class="nc"><i>57</i>&nbsp; visited.add(square);</b>
        <b class="nc"><i>58</i>&nbsp; addNewTargets(traveller, targets, visited, node, square);</b>
        <b class="nc"><i>59</i>&nbsp; }</b>
        <b class="nc"><i>60</i>&nbsp; return null;</b>
        <i>61</i>&nbsp; }
        <i>62</i>&nbsp;
        <i>63</i>&nbsp; private static void addNewTargets(Unit traveller, List&lt;Node&gt; targets,
        <i>64</i>&nbsp; Set&lt;Square&gt; visited, Node node, Square square) {
        <b class="nc"><i>65</i>&nbsp; for (Direction direction : Direction.values()) {</b>
        <b class="nc"><i>66</i>&nbsp; Square target = square.getSquareAt(direction);</b>
        <b class="nc"><i>67</i>&nbsp; if (!visited.contains(target)</b>
        <b class="nc"><i>68</i>&nbsp; &amp;&amp; (traveller == null || target.isAccessibleTo(traveller))) {</b>
        <b class="nc"><i>69</i>&nbsp; targets.add(new Node(direction, target, node));</b>
        <i>70</i>&nbsp; }
        <i>71</i>&nbsp; }
        <i>72</i>&nbsp; }
        <i>73</i>&nbsp;
        <i>74</i>&nbsp; /**
        <i>75</i>&nbsp; * Finds the nearest unit of the given type and returns its location. This
        <i>76</i>&nbsp; * method will perform a breadth first search starting from the given
        <i>77</i>&nbsp; * square.
        <i>78</i>&nbsp; *
        <i>79</i>&nbsp; * @param type
        <i>80</i>&nbsp; * The type of unit to search for.
        <i>81</i>&nbsp; * @param currentLocation
        <i>82</i>&nbsp; * The starting location for the search.
        <i>83</i>&nbsp; * @return The nearest unit of the given type, or &lt;code&gt;null&lt;/code&gt; if no
        <i>84</i>&nbsp; * such unit could be found.
        <i>85</i>&nbsp; */
        <i>86</i>&nbsp; public static Unit findNearest(Class&lt;? extends Unit&gt; type,
        <i>87</i>&nbsp; Square currentLocation) {
        <b class="nc"><i>88</i>&nbsp; List&lt;Square&gt; toDo = new ArrayList&lt;&gt;();</b>
        <b class="nc"><i>89</i>&nbsp; Set&lt;Square&gt; visited = new HashSet&lt;&gt;();</b>
        <i>90</i>&nbsp;
        <b class="nc"><i>91</i>&nbsp; toDo.add(currentLocation);</b>
        <i>92</i>&nbsp;
        <b class="nc"><i>93</i>&nbsp; while (!toDo.isEmpty()) {</b>
        <b class="nc"><i>94</i>&nbsp; Square square = toDo.remove(0);</b>
        <b class="nc"><i>95</i>&nbsp; Unit unit = findUnit(type, square);</b>
        <b class="nc"><i>96</i>&nbsp; if (unit != null) {</b>
        <b class="nc"><i>97</i>&nbsp; assert unit.hasSquare();</b>
        <b class="nc"><i>98</i>&nbsp; return unit;</b>
        <i>99</i>&nbsp; }
        <b class="nc"><i>100</i>&nbsp; visited.add(square);</b>
        <b class="nc"><i>101</i>&nbsp; for (Direction direction : Direction.values()) {</b>
        <b class="nc"><i>102</i>&nbsp; Square newTarget = square.getSquareAt(direction);</b>
        <b class="nc"><i>103</i>&nbsp; if (!visited.contains(newTarget) &amp;&amp; !toDo.contains(newTarget)) {</b>
        <b class="nc"><i>104</i>&nbsp; toDo.add(newTarget);</b>
        <i>105</i>&nbsp; }
        <i>106</i>&nbsp; }
        <b class="nc"><i>107</i>&nbsp; }</b>
        <b class="nc"><i>108</i>&nbsp; return null;</b>
        <i>109</i>&nbsp; }
        <i>110</i>&nbsp;
        <i>111</i>&nbsp; /**
        <i>112</i>&nbsp; * Finds a subtype of Unit in a level.
        <i>113</i>&nbsp; * This method is very useful for finding the ghosts in the parsed map.
        <i>114</i>&nbsp; *
        <i>115</i>&nbsp; * @param clazz the type to search for.
        <i>116</i>&nbsp; * @param board the board to find the unit in.
        <i>117</i>&nbsp; * @param &lt;T&gt; the return type, same as the type in clazz.
        <i>118</i>&nbsp; *
        <i>119</i>&nbsp; * @return the first unit found of type clazz, or null.
        <i>120</i>&nbsp; */
        <i>121</i>&nbsp; public static &lt;T extends Unit&gt; T findUnitInBoard(Class&lt;T&gt; clazz, Board board) {
        <b class="nc"><i>122</i>&nbsp; for (int y = 0; y &lt; board.getHeight(); y++) {</b>
        <b class="nc"><i>123</i>&nbsp; for (int x = 0; x &lt; board.getWidth(); x++) {</b>
        <b class="nc"><i>124</i>&nbsp; final T ghost = Navigation.findUnit(clazz, board.squareAt(x, y));</b>
        <b class="nc"><i>125</i>&nbsp; if (ghost != null) {</b>
        <b class="nc"><i>126</i>&nbsp; return ghost;</b>
        <i>127</i>&nbsp; }
        <i>128</i>&nbsp; }
        <i>129</i>&nbsp; }
        <i>130</i>&nbsp;
        <b class="nc"><i>131</i>&nbsp; return null;</b>
        <i>132</i>&nbsp; }
        <i>133</i>&nbsp;
        <i>134</i>&nbsp; /**
        <i>135</i>&nbsp; * Determines whether a square has an occupant of a certain type.
        <i>136</i>&nbsp; *
        <i>137</i>&nbsp; * @param type
        <i>138</i>&nbsp; * The type to search for.
        <i>139</i>&nbsp; * @param square
        <i>140</i>&nbsp; * The square to search.
        <i>141</i>&nbsp; * @param &lt;T&gt;
        <i>142</i>&nbsp; * the type of unit we searched for.
        <i>143</i>&nbsp; *
        <i>144</i>&nbsp; * @return A unit of type T, iff such a unit occupies this square, or
        <i>145</i>&nbsp; * &lt;code&gt;null&lt;/code&gt; of none does.
        <i>146</i>&nbsp; */
        <i>147</i>&nbsp; @SuppressWarnings(&quot;unchecked&quot;)
        <i>148</i>&nbsp; public static &lt;T extends Unit&gt; T findUnit(Class&lt;T&gt; type, Square square) {
        <b class="nc"><i>149</i>&nbsp; for (Unit unit : square.getOccupants()) {</b>
        <b class="nc"><i>150</i>&nbsp; if (type.isInstance(unit)) {</b>
        <b class="nc"><i>151</i>&nbsp; assert unit.hasSquare();</b>
        <b class="nc"><i>152</i>&nbsp; return (T) unit;</b>
        <i>153</i>&nbsp; }
        <b class="nc"><i>154</i>&nbsp; }</b>
        <b class="nc"><i>155</i>&nbsp; return null;</b>
        <i>156</i>&nbsp; }
        <i>157</i>&nbsp;
        <i>158</i>&nbsp; /**
        <i>159</i>&nbsp; * Helper class to keep track of the path.
        <i>160</i>&nbsp; *
        <i>161</i>&nbsp; * @author Jeroen Roosen
        <i>162</i>&nbsp; */
        <b class="nc"><i>163</i>&nbsp; private static final class Node {</b>
        <i>164</i>&nbsp;
        <i>165</i>&nbsp; /**
        <i>166</i>&nbsp; * The direction for this node, which is &lt;code&gt;null&lt;/code&gt; for the root
        <i>167</i>&nbsp; * node.
        <i>168</i>&nbsp; */
        <i>169</i>&nbsp; private final Direction direction;
        <i>170</i>&nbsp;
        <i>171</i>&nbsp; /**
        <i>172</i>&nbsp; * The parent node, which is &lt;code&gt;null&lt;/code&gt; for the root node.
        <i>173</i>&nbsp; */
        <i>174</i>&nbsp; private final Node parent;
        <i>175</i>&nbsp;
        <i>176</i>&nbsp; /**
        <i>177</i>&nbsp; * The square associated with this node.
        <i>178</i>&nbsp; */
        <i>179</i>&nbsp; private final Square square;
        <i>180</i>&nbsp;
        <i>181</i>&nbsp; /**
        <i>182</i>&nbsp; * Creates a new node.
        <i>183</i>&nbsp; *
        <i>184</i>&nbsp; * @param direction
        <i>185</i>&nbsp; * The direction, which is &lt;code&gt;null&lt;/code&gt; for the root
        <i>186</i>&nbsp; * node.
        <i>187</i>&nbsp; * @param square
        <i>188</i>&nbsp; * The square.
        <i>189</i>&nbsp; * @param parent
        <i>190</i>&nbsp; * The parent node, which is &lt;code&gt;null&lt;/code&gt; for the root
        <i>191</i>&nbsp; * node.
        <i>192</i>&nbsp; */
        <b class="nc"><i>193</i>&nbsp; Node(Direction direction, Square square, Node parent) {</b>
        <b class="nc"><i>194</i>&nbsp; this.direction = direction;</b>
        <b class="nc"><i>195</i>&nbsp; this.square = square;</b>
        <b class="nc"><i>196</i>&nbsp; this.parent = parent;</b>
        <i>197</i>&nbsp; }
        <i>198</i>&nbsp;
        <i>199</i>&nbsp; /**
        <i>200</i>&nbsp; * @return The direction for this node, or &lt;code&gt;null&lt;/code&gt; if this
        <i>201</i>&nbsp; * node is a root node.
        <i>202</i>&nbsp; */
        <i>203</i>&nbsp; private Direction getDirection() {
        <b class="nc"><i>204</i>&nbsp; return direction;</b>
        <i>205</i>&nbsp; }
        <i>206</i>&nbsp;
        <i>207</i>&nbsp; /**
        <i>208</i>&nbsp; * @return The square for this node.
        <i>209</i>&nbsp; */
        <i>210</i>&nbsp; private Square getSquare() {
        <b class="nc"><i>211</i>&nbsp; return square;</b>
        <i>212</i>&nbsp; }
        <i>213</i>&nbsp;
        <i>214</i>&nbsp; /**
        <i>215</i>&nbsp; * @return The parent node, or &lt;code&gt;null&lt;/code&gt; if this node is a root
        <i>216</i>&nbsp; * node.
        <i>217</i>&nbsp; */
        <i>218</i>&nbsp; private Node getParent() {
        <b class="nc"><i>219</i>&nbsp; return parent;</b>
        <i>220</i>&nbsp; }
        <i>221</i>&nbsp;
        <i>222</i>&nbsp; /**
        <i>223</i>&nbsp; * Returns the list of values from the root of the tree to this node.
        <i>224</i>&nbsp; *
        <i>225</i>&nbsp; * @return The list of values from the root of the tree to this node.
        <i>226</i>&nbsp; */
        <i>227</i>&nbsp; private List&lt;Direction&gt; getPath() {
        <b class="nc"><i>228</i>&nbsp; if (parent == null) {</b>
        <b class="nc"><i>229</i>&nbsp; return new ArrayList&lt;&gt;();</b>
        <i>230</i>&nbsp; }
        <b class="nc"><i>231</i>&nbsp; List&lt;Direction&gt; path = parent.getPath();</b>
        <b class="nc"><i>232</i>&nbsp; path.add(getDirection());</b>
        <b class="nc"><i>233</i>&nbsp; return path;</b>
        <i>234</i>&nbsp; }
        <i>235</i>&nbsp; }
        <i>236</i>&nbsp;}
    </div>
</div>

<div class="footer">

    <div style="float:right;">generated on 2023-04-25 16:45</div>
</div>
</body>
</html>
